package DifficultPractice;

public class Demo32 {
	
	public static void main(String[] args){
		
		String s = ")()())()()(";
		String x = "00204002040";
//		System.out.print(s);
//		System.out.println(s.charAt(2));
		int res = longestValidParentheses(s);
		System.out.println(res);
	}
	
	
	private static int longestValidParentheses(String s) {
		
		if(s == "" || s == ")")	return 0;
		
		int[] dp = new int[s.length() + 1];
//		for(int i=0; i<dp.length;i++)
//			System.out.print(dp[i]);
//		System.out.println();
		
		int res = 0;
	
		for(int i=2; i<dp.length; i++) {
			int s_i = i-1;
			if(s.charAt(s_i) == '(')
				//
				dp[i] = 0;
			
			else {
				if(s.charAt(s_i-1) == '(')
					dp[i] = dp[i-2] + 2;
				else {
					
					if(s_i - 1 - dp[i-1] < 0 || s.charAt(s_i - 1 - dp[i-1]) == ')')
						dp[i] = 0;
					
					else
						dp[i] = dp[i-1] + dp[i-1-dp[i-1]-1] + 2;
						
				}
			}
			
			if(dp[i] > res)
				res = dp[i];
			
		}
//		for(int i=0; i<dp.length;i++)
//			System.out.print(dp[i]);
//		System.out.println();
//		
		
		return res;
		
    }
	
	
}
